//Tue 19 Jan 2010 05:49:46 PM CST 
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class ParkAmusement
{
public:
	void compute(int index)
	{
		if (computed[index]) return; // Already computed
		if (landings[index][index]=='E') { DP[index][0] = 1.0; computed[index] = true; return;} // Exit
		if (landings[index][index]=='P') { computed[index] = true; return;} // Crocodile Pond
	
	 	// Vertex has outgoing edges to other vertices
		int cnt = 0;
		for (int i = 0; i < N; i++)
			if (landings[index][i] == '1')
			{
				if (!computed[i]) // Make sure everything you need to compute DP[index][] has been computed
					compute(i);
				for (int j = 1; j <= K; j++)
					DP[index][j] += DP[i][j-1];
				cnt++;
			}
		for (int j = 1; j <= K; j++)
			DP[index][j] /= double(cnt);
		computed[index] = true;
	}
	double getProbability(vector <string> land, int startLanding, int k)
	{
		landings = land;
		N = landings.size();
		K = k;
		for(int i=0; i<N; i++)
			computed.push_back(false);
		for(int i=0; i<N; i++)
		{
			vector<double> temp(N, 0.0);
			DP.push_back(temp);
		}
		double sum = 0.0;
		for (int i = 0; i < N; i++)
		{
			compute(i); 
			sum += DP[i][K]; 
		}
		return (DP[startLanding][K]/sum);
	}
	int N;
	int K;
	vector<bool> computed;
	vector<vector<double> > DP;
	vector <string> landings;
};
